LinkedList 源码分析

结构体系

1
2
3
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList继承自AbstractSequentialList，并同时实现了List、Deque、Cloneable与Serializable接口。从继承体系上与接口上，可以看出LinkedList不仅仅是双向链表而已，它可以同时被当做双向队列进行操作。

为什么是双向链表呢？后面一小节将会解释。

常量与重要成员

1
2
3
4
5
6
// 记录链表上实际装载的节点个数
transient int size = 0;
// 指向链表头部的指针
transient Node<E> first;
// 指向链表尾部的指针
transient Node<E> last;

在成员变量中，我们可以看到链表所承载的节点是Node，下面看看Node是怎么构成的。

1
2
3
4
5
6
7
8
9
10
11
private static class Node<E> {
    E item; // 节点上承载的值
    Node<E> next; // 指向前一个节点
    Node<E> prev; // 指向后一个节点

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

从Node中，不难看出LinkedList就是一个双向链表的集合，如下所示。

构造函数

1
2
3
4
5
6
7
public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

LinkedList的构造函数可以说是很简约了，毕竟内部不像ArrayList里面还有个数组作支撑，只需头/尾指针即可。

基本操作 - node()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 在LinkedList中，在某些需要在指定节点中进行操作的时候，是怎么通过索引下标的形式找到指定节点的呢
// LinkedList内部提供了node()方法来实现这一目标。顺便一提node()内部充分使用了头尾节点的好处，将遍历范围缩减到size/2内
Node<E> node(int index) {
    // assert isElementIndex(index);
	
  	// 若index > size/2
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

添加操作 - add()

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean add(E e) {
    linkLast(e);
    return true;
}

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
      linkLast(element);
    else
      linkBefore(element, node(index));
}

上面的add()方法均调用了link*（）字样的方法，其实这是LinkedList内部用于对链表的中单个节点的操作。相对应的remove()方法也会调用unlink*()字样的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 作为头节点链接到链表中
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
  	// 若f为null, 则表明链表为空
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

// 作为尾节点链接到链表中
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
  	// 若l为null, 则表明链表为空
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

// 将新节点插在指定节点前
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

LinkedList也提供了将一组数据添加入链表中的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public boolean addAll(Collection<? extends E> c) {
  	// 默认从尾节点后插入
  	return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
      return false;

    Node<E> pred, succ;
  	// 若指定位置就是尾节点时
    if (index == size) {
      succ = null;
      pred = last;
    } else {
      succ = node(index);
      pred = succ.prev;
    }

    for (Object o : a) {
      @SuppressWarnings("unchecked") E e = (E) o;
      Node<E> newNode = new Node<>(pred, e, null);
      // 确保头节点始终不为空
      if (pred == null)
      	first = newNode;
      else
        pred.next = newNode;
      pred = newNode;
    }

  	// 确保尾节点不为空
    if (succ == null) {
      last = pred;
    } else {
      pred.next = succ;
      succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

删除操作 - remove()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public E remove() {
    return removeFirst();
}

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
    
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
    	throw new NoSuchElementException();
    return unlinkFirst(f);
}

public E removeLast() {
	final Node<E> l = last;
	if (l == null)
		throw new NoSuchElementException();
	return unlinkLast(l);
}

remove()如同add()一样，使用着功能截然相反的unlink*()方法，但逻辑处理难度上较大与link*()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// 删除非空头节点
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // 方便GC进行垃圾回收
    first = next;
  	// 若链表中只有单个节点
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

// 删除非空尾节点
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // 方便GC进行垃圾回收
    last = prev;
  	// 若链表中只有单个节点
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

// 删除指定节点
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

  	// 若prev指向的上一个节点为空，那么该节点为头节点
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

  	// 若next指向的下一个节点为空，那么该节点为尾节点
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

remove()操作中还提供了根据给定值删除指定节点的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean remove(Object o) {
    // 若给定值为null
    if (o == null) {
    	// 在这里就不能缩减范围提高效率了，只能老实的进行从头遍历到尾
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
              	unlink(x);
              	return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
              	unlink(x);
              	return true;
            }
        }
    }
    return false;
}

查询操作 - get()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

public E getFirst() {
	final Node<E> f = first;
	if (f == null)
		throw new NoSuchElementException();
	return f.item;
}

public E getLast() {
	final Node<E> l = last;
	if (l == null)
		throw new NoSuchElementException();
	return l.item;
}

修改操作 - set()

1
2
3
4
5
6
7
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

实现了Deque接口的相关操作

别忘了，LinkedList实现了Deque接口，这说明操作LinkedList也可以像操作双向队列一样。如同*first()以及*last()这种操作也属于Deque要求实现的，下面将列出别的方法。

1
2
3
4
5
6
7
8
9
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

public E poll() {
	final Node<E> f = first;
	return (f == null) ? null : unlinkFirst(f);
}